package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的序列化与反序列化
 *
 * @Author: waxijiang
 * @Date: 2021/6/7
 */
public class BinarySerialize {
    public static void main(String[] args) {
        BinarySerialize binarySerialize = new BinarySerialize();
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(3);
        treeNode.left.left = new TreeNode(5);
        String serialize = binarySerialize.serialize(treeNode);
        System.out.println(serialize);
        TreeNode deserialize = binarySerialize.deserialize(serialize);
        System.out.println(deserialize);
    }

    public String serialize(TreeNode root) {
        if (root == null) {
            return "null";
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int layer = 0;
        int count = 0;
        boolean hasNextLayer = false;
        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            count++;
            if (node != null) {
                result.append(node.val).append(",");
                queue.add(node.left);
                queue.add(node.right);

                if (node.left != null || node.right != null) {
                    hasNextLayer = true;
                }
            } else {
                result.append("null,");
                queue.add(null);
                queue.add(null);
            }
            if (count == Math.pow(2, layer)) {
                count = 0;
                layer++;
                if (node == null && !hasNextLayer) {
                    break;
                }
                hasNextLayer = false;
            }
        }
        return result.toString().substring(0, result.length() - 1);
    }

    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        return buildTree(split, 1);
    }

    public TreeNode buildTree(String[] split, int start) {
        if (start <= split.length && !"null".equals(split[start - 1])) {
            TreeNode root = new TreeNode(Integer.parseInt(split[start - 1]));
            root.left = buildTree(split, start * 2);
            root.right = buildTree(split, start * 2 + 1);
            return root;
        } else {
            return null;
        }
    }
}
